10175. 「一本通 5.5 例 1」滑动窗口

题意

给一个长度为 $N$ 的数组，一个长为 $K$ 的滑动窗体从最左端移至最右端，你只能看到窗口中的 $K$ 个数，每次窗体向右移动一位，你的任务是找出窗体在各个位置时的最大值和最小值。

思路

DP水过去。。。
加上优先队列优化。。。

#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000010],h,t,f1[1000010],f2[1000010];
struct node{
	int x,id;
}q[1000010];
void dp1(){
	h=t=0;
	for(int i=1;i<=n;i++){
		while(h<=t&&i-q[h].id+1>k) h++;
		while(h<=t&&a[i]<=q[t].x) t--;
		q[++t].id=i;
		q[t].x=a[i]; 
		f1[i]=q[h].x;
	}
}
void dp2(){
	h=t=0;
	for(int i=1;i<=n;i++){
		while(h<=t&&i-q[h].id+1>k) h++;
		while(h<=t&&a[i]>=q[t].x) t--;
		q[++t].id=i;
		q[t].x=a[i]; 
		f2[i]=q[h].x;
	}
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	fill(f1,f1+1000005,2e9);
	fill(f2,f2+1000005,-2e9);
	dp1();dp2();
	for(int i=k;i<=n;i++){
		cout<<f1[i]<<" ";
	}cout<<endl;
	for(int i=k;i<=n;i++){
		cout<<f2[i]<<" ";
	}cout<<endl;
	return 0;
}